package com.fmistuff.threadedcalc;
import java.util.List;
import java.util.LinkedList;
import java.math.BigInteger;

public class ExpressionTree
{
	/*
	 * The root node of the expression tree.
	 */
	public ExpressionNode rootNode;
	
	
	public ExpressionTree(BigInteger value)
	{
		rootNode = new ExpressionNodeSimple(value);
	}
	
	public ExpressionTree(ExpressionTree left, ExpressionTree right, ExpressionOperands operand)
	{
		rootNode = new ExpressionNode(left.rootNode, right.rootNode, operand);
	}
	
	public ExpressionTree(String expression) throws Exception
	{
		rootNode = Parse(expression);
	}
	
	private ExpressionNode Parse(String expression) throws Exception
	{
		List<ExpressionNode> nodes = new LinkedList<ExpressionNode>();
		List<ExpressionOperands> operands = new LinkedList<ExpressionOperands>();
		
		// Parse the whole string to nodes and operands
		for (int i=0; i < expression.length(); i++)
		{
			// Parse brackets
			if (expression.charAt(i) == '(')
			{
				int depth = 1;
				int j = i+1;
				for (; j < expression.length() && depth > 0; j++)
					if (expression.charAt(j) == '(')
						depth++;
					else if (expression.charAt(j) == ')')
						depth--;
				
				if (depth > 0)
					throw new Exception("Incorrect brackets!");
				
				String subExpr = expression.substring(i+1, j-1);
				ExpressionNode subExprNode = Parse(subExpr);
				nodes.add(subExprNode);
				
				i = j - 1;
			}
			
			// Parse numbers
			else if (expression.charAt(i) >= '0' && expression.charAt(i) <= '9')
			{
				int j = i+1;
				for (;j < expression.length();j++)
					if (expression.charAt(j) < '0' || expression.charAt(j) > '9')
						break;
				
				String numExpr = expression.substring(i, j);
				BigInteger num = new BigInteger(numExpr);
				ExpressionNode numExprNode = new ExpressionNodeSimple(num);
				nodes.add(numExprNode);
				
				i = j - 1;
			}
			
			// Parse operands
			else if (expression.charAt(i) == '+')
				operands.add(ExpressionOperands.Add);
			else if (expression.charAt(i) == '-')
				operands.add(ExpressionOperands.Subtract);
			else if (expression.charAt(i) == '*')
				operands.add(ExpressionOperands.Multiply);
			else if (expression.charAt(i) == '/')
				operands.add(ExpressionOperands.Divide);
		}
		
		// Check consistency
		if (nodes.size() != operands.size() + 1)
			throw new Exception("Number of operands does not match number of expressions!");
		
		// Construct the tree
		while (nodes.size() > 1)
		{
			// Find operand with highest priority
			int pos = 0;
			int maxPriority = 0;
			int maxPosition = 0;
			for (ExpressionOperands expressionOperands : operands)
			{
				if (expressionOperands.GetPriority() > maxPriority)
				{
					maxPriority = expressionOperands.GetPriority();
					maxPosition = pos;
				}
				pos++;
			}
			
			// Take the nodes and the operand
			ExpressionOperands operand = operands.remove(maxPosition);
			ExpressionNode leftNode = nodes.remove(maxPosition);
			ExpressionNode rightNode = nodes.remove(maxPosition);
			
			// Construct the new node
			ExpressionNode newNode = new ExpressionNode(leftNode, rightNode, operand);
			nodes.add(maxPosition, newNode);
		}

		return nodes.get(0);
	}
}
